package greedy;

import java.util.Arrays;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/27 23:45
 * https://leetcode-cn.com/problems/candy/
 */
public class Candy {

    /**
     * 采用了两次贪心的策略：
     * 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。 符合左规则
     * 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。 符合右规则
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        //1、给每个学生都分配一个糖果
        int[] result = new int[ratings.length];
        int sum = 0;
        Arrays.fill(result, 1);
        //左到右遍历，符合左规则A<B
        for (int i = 0; i < ratings.length - 1; i++) {
            if (ratings[i + 1] > ratings[i]) {
                result[i + 1] = result[i] + 1;
            }
        }
        //从右往左遍历，符合右规则A>B
        for (int i = ratings.length - 1; i > 0; i--) {
            if (ratings[i - 1] > ratings[i]) {
                result[i - 1] = Math.max(result[i-1], result[i] + 1);
            }
            sum += result[i];
        }
        return sum + result[0];
    }

    public static void main(String[] args) {

    }
}
